Straż pożarna

Limit pamięci: 64 MB

W stolicy Bajtocji, Bajtawie, ulice mają bardzo regularny układ. Wszystkie biegną albo z północy na południe, albo z zachodu na wschód. Łatwo zauważyć, że każda ulica z północy na południe przecina każdą ulicę z zachodu na wschód w dokładnie jednym miejscu. Ponadto, wzdłuż każdej ulicy kolejne skrzyżowania są odległe o dokładnie 1 km.

W Bajtawie jest zabytkowych budynków, z których każdy znajduje się przy jednym ze skrzyżowań. Radzie Miejskiej bardzo zależy na ochronie tych unikalnych zabytków, dlatego postanowiono wybudować w mieście dwa duże posterunki straży pożarnej. Każdy z zabytków będzie chroniony przez posterunek jemu najbliższy; w przypadku równych odległości od każdego z posterunków, budynek będzie pod ochroną ich obu.

Zabudowa w Bajtawie jest bardzo gęsta. Nie należy więc patrzeć na odległość do zabytków w linii prostej. Zamiast tego, jako odległość od posterunku do zabytku należy przyjąć długość najkrótszej trasy biegnącej ulicami.

Rada Miejska przygotowała kilka projektów lokalizacji posterunków straży. Zostałeś poproszony o wyznaczenie, dla każdego z nich, liczby zabytków chronionych: tylko przez pierwszy posterunek, tylko przez drugi posterunek oraz przez oba posterunki.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się cztery liczby całkowite , , oraz (, ) pooddzielane pojedynczymi odstępami, oznaczające odpowiednio: liczbę ulic biegnących z północy na południe, liczbę ulic biegnących z zachodu na wschód, liczbę zabytkowych budynków w Bajtawie oraz liczbę projektów zaproponowanych przez Radę Miejską. Ulice biegnące z północy na południe są ponumerowane od do , w kierunku z zachodu na wschód. Ulice biegnące z zachodu na wschód są ponumerowane od do , w kierunku z północy na południe. Skrzyżowaniu -tej ulicy biegnącej z północy na południe z -tą ulicą biegnącą z zachodu na wschód dla uproszczenia przypisujemy współrzędne .

W każdym z kolejnych wierszy znajdują się dwie liczby całkowite oraz (, ) oddzielone pojedynczym odstępem i oznaczające współrzędne -tego zabytku. Żadna para zabytków nie znajduje się przy tym samym skrzyżowaniu.

Każdy z kolejnych wierszy zawiera jedną propozycję Rady Miejskiej - cztery liczby całkowite , , , pooddzielane pojedynczymi odstępami, , , . Współrzędne oraz opisują skrzyżowania, przy których mają być umiejscowione posterunki straży zgodnie z -tą propozycją ().

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy. W -tym wierszu powinny się znaleźć trzy liczby całkowite, oznaczające: liczbę zabytków chronionych tylko przez pierwszy posterunek z -tej propozycji Rady Miejskiej, liczbę zabytków chronionych tylko przez drugi posterunek oraz liczbę budynków chronionych przez oba posterunki. Liczby te powinny być oddzielone pojedynczymi odstępami.

Przykład

Dla danych wejściowych:

6 5 6 1
1 2
6 5
5 1
3 3
3 4
4 1
2 3 4 3

poprawną odpowiedzią jest:

1 3 2

Na rysunku linie przerywane przedstawiają ulice, kółka - lokalizacje zabytków, a krzyżyki - proponowane lokalizacje posterunków straży pożarnej. Białe kółko przedstawia zabytek chroniony przez pierwszy posterunek, czarne kółka - przez drugi posterunek, natomiast szare kółka - przez oba posterunki.

Autorzy zadania: Marian M. Kędzierski, Jakub Radoszewski.